public class ArrayList implements List {

	private static final int DEFAULT_CAPACITY = 10;

	private Object[] items;
	private int size;

	public ArrayList() {
		init(DEFAULT_CAPACITY);
	}

	public ArrayList(int capacity) {
		if (capacity < 0) {
			throw new IllegalArgumentException();
		}
		init(capacity);
	}

	private void init(int capacity) {
		items = new Object[capacity];
		size = 0;
	}

	public int size( ) {
		return size;
	}
    
    public boolean isEmpty( ) {
		return (size == 0);
	}
    
    public boolean contains( Object x ) {
		return (findPos(x) >= 0);
	}

	private int findPos(Object x) {
		for (int i=0; i < size; ++i) {
			if (x == null) {
				if (items[i] == null) {
					return i;
				}
			}
			else if (x.equals(items[i])) {
				return i;
			}
		}
		return -1;
	}
    
    public boolean add( Object x ) {
		if (items.length == size) {
			grow();
		}
		items[ size++ ] = x;
		return true;
	}

	private void grow() {
		Object[] newItems = new Object[items.length * 2 + 1];
		for (int i=0; i < size; ++i) {
			newItems[i] = items[i];
		}
		items = newItems;
	}
    
    public boolean remove( Object x ) {
		int pos = findPos(x);
		if (pos >= 0) {
			remove(pos);
			return true;
		}
		else {
			return false;
		}
	}

	private void remove(int pos) {
		for (int i=pos+1; i < size; ++i) {
			items[ i - 1 ] = items[ i ];
		}
		items[ --size ] = null;
	}
    
    public void clear( ) {
		for (int i=0; i < size; ++i) {
			items[ i ] = null;
		}
		size = 0;
	}
    
    public Iterator iterator( ) {
		return new ArrayListIterator(this, 0);
	}
    
    public Object [ ] toArray( ) {
		Object[] copy = new Object[size];
		for (int i=0; i < size; ++i) {
			copy[i] = items[i];
		}
		return copy;
	}

    public Object get( int idx ) {
		if (idx >= 0 && idx < size) {
			return items[ idx ];
		}
		else {
			throw new IndexOutOfBoundsException();
		}
	}
        
    public Object set( int idx, Object newVal ) {
		if (idx >= 0 && idx < size) {
			Object oldVal = items[ idx ];
			items[ idx ] = newVal;
			return oldVal;
		}
		else {
			throw new IndexOutOfBoundsException();
		}
	}
    
    public ListIterator listIterator( int pos ) {
		if (pos >= 0 && pos <= size) {
			return new ArrayListIterator(this, pos);
		}
		else {
			throw new IndexOutOfBoundsException();
		}
	}

	private static class ArrayListIterator implements ListIterator {

		private static final int NONE = 0;
		private static final int NEXT = 1;
		private static final int PREV = 2;
		
		private ArrayList alist;
		private int pos;
		private int lastOp;

		public ArrayListIterator(ArrayList _alist, int _pos) {
			alist = _alist;
			pos = _pos;
			lastOp = NONE;
		}

	    public boolean hasNext( ) {
			return (pos < alist.size);
		}
    
    	public Object next( ) {
			if (!hasNext()) {
				throw new IllegalStateException();
			}
			lastOp = NEXT;
			return alist.items[pos++];
		}

	    public boolean hasPrevious( ) {
			return (pos > 0);
		}
    
    	public Object previous( ) {
			if (!hasPrevious()) {
				throw new IllegalStateException();
			}
			lastOp = PREV;
			return alist.items[--pos];
		}
    
    	public void remove( ) {
			switch (lastOp) {
				case NONE:
					throw new IllegalStateException();
				case NEXT:
					alist.remove(--pos);
					lastOp = NONE;
					break;
				case PREV:
					alist.remove(pos);
					lastOp = NONE;
					break;
			}
		}
	}
}